package 排序算法;

import java.util.Arrays;

/**
 * Created by hest0 on 2017/4/21.
 */
public class 归并排序2 {

    public static void main(String[] args) {
        int[] a = new int[]{4, 3, 6, 1, 2, 5, -10, 100, -99, 1000};
        System.out.println(Arrays.toString(a));
        new MergeSort().mergeSort_toUp(a, 0, 1);
        System.out.println(Arrays.toString(a));
        System.out.println("=====================================");
        int[] b = new int[]{4, 3, 6, 1, 2, 5, -10, 100, -99, 1000};
        System.out.println(Arrays.toString(b));
        new MergeSort().mergeSort_toDown(b, 0, b.length - 1);
        System.out.println(Arrays.toString(b));
        System.out.println("=====================================");
        int[] c = new int[]{4, 3, 6, 1, 2, 5, -10, 100, -99, 1000};
        System.out.println(Arrays.toString(c));
        new MergeSort().mergeSort_toUp2(c);
        System.out.println(Arrays.toString(c));
    }

    private static class MergeSort {
        /**
         * 自下向上的归并算法2
         *
         * @param a
         */
        public void mergeSort_toUp2(int[] a) {
            int n = a.length;
            for (int i = 1; i < n; i = i + i)
                for (int j = 0; j < n - i; j += i + i)
                    merge_2(a, j, j + i - 1, Math.min(j + i + i - 1, n - 1));
        }

//-------------------------------------------------------------------
//-------------------------------------------------------------------

        /**
         * 自下向上的归并，步长逐渐增加
         *
         * @param a
         * @param l
         * @param g
         */
        private void mergeSort_toUp(int[] a, int l, int g) {
            int n = a.length;
//            int mid = n / (g << 1);
//            int c = n & ((g << 1) - 1);
            int mid = n / (g * 2);
            int r = n % (g * 2);

            if (mid == 0)
                return;

            for (int i = 0; i < mid; ++i) {
                l = i * 2 * g;
                merge_1(a, l, l + g, (g << 1) + l - 1);
            }
            if (r != 0)
                merge_1(a, n - r - 2 * g, n - r, n - 1);

            mergeSort_toUp(a, 0, 2 * g);
        }

        /**
         * 二路归并：将2个有序表归并成一个有序表，适用于自下而上的归并
         */
        private void merge_1(int[] a, int l, int m, int r) {
            int[] tmp = new int[r - l + 1];
            int i = l, j = m, idx = 0;
            while (i < m && j <= r)
                tmp[idx++] = a[i] <= a[j] ? a[i++] : a[j++];
            while (i < m)
                tmp[idx++] = a[i++];
            while (j <= r)
                tmp[idx++] = a[j++];
            System.arraycopy(tmp, 0, a, l, tmp.length);
        }

//-------------------------------------------------------------------
//-------------------------------------------------------------------

        /**
         * 自上向下的归并，步长逐渐减小
         *
         * @param a
         * @param l
         * @param r
         */
        private void mergeSort_toDown(int[] a, int l, int r) {
            if (l < r) {
                int m = (l + r) / 2;
                mergeSort_toDown(a, l, m);
                mergeSort_toDown(a, m + 1, r);
                merge_2(a, l, m, r);
            }
        }

        /**
         * 二路归并：将2个有序表归并成一个有序表，适用于自上而下的归并
         */
        private void merge_2(int[] a, int l, int m, int r) {
            int[] tmp = new int[r - l + 1];
            int i = l, j = m + 1, idx = 0;
            while (i <= m && j <= r)
                tmp[idx++] = a[i] <= a[j] ? a[i++] : a[j++];
            while (i <= m)
                tmp[idx++] = a[i++];
            while (j <= r)
                tmp[idx++] = a[j++];
            System.arraycopy(tmp, 0, a, l, tmp.length);
        }
    }
}




